package day20210629;

import treenode.SimpleTreeNode;

/**
 * 404. 左叶子之和
 * @author lizy4
 * @date 2021/6/29 10:45
 */
public class Solution2 {

    public static void main(String[] args) {
        Solution2 solution = new Solution2();
        SimpleTreeNode simpleTreeNode = new SimpleTreeNode();
        simpleTreeNode.val = 6;
        simpleTreeNode.right = new SimpleTreeNode(8);
        simpleTreeNode.right.right = new SimpleTreeNode(9);
        simpleTreeNode.right.left = new SimpleTreeNode(7);
        simpleTreeNode.left = new SimpleTreeNode(2);
        simpleTreeNode.left.left = new SimpleTreeNode(2);
        System.out.println(solution.sumOfLeftLeaves(simpleTreeNode));
    }

    private int sumOfLeftLeaves(SimpleTreeNode root) {
        // root为空则返回0，不为空则向下遍历
        return root != null ? dfs(root) : 0;
    }

    private int dfs(SimpleTreeNode node) {
        int ans = 0;
        // 左节点不为空
        if (node.left != null) {
            // 如果左节点是叶子节点，则加上叶子的值
            // 如果不是叶子节点，则继续往下遍历
            ans += isLeafNode(node.left) ? node.left.val : dfs(node.left);
        }
        // 如果右节点不为空，且右节点不是叶子节点
        if (node.right != null && !isLeafNode(node.right)) {
            // 遍历右节点
            ans += dfs(node.right);
        }
        return ans;
    }

    /**
     * 判断是否是叶子节点
     *
     * @param node 节点
     * @return boolean
     */
    private boolean isLeafNode(SimpleTreeNode node) {
        return node.left == null && node.right == null;
    }
}
